package jianzhiOffer;

/**
 * 剑指 Offer 25. 合并两个排序的链表
 */
public class T00025 {
    public static void main(String[] args) {
        ListNode l1 = build(1,2,3);
        ListNode l2 = build(1,2,4);

        ListNode l3 = new Solution().mergeTwoLists(l1, l2);

        print(l3);
    }

    static void print(ListNode head) {
        if(head == null)
            return ;
        ListNode c = head;
        while(true) {
            System.out.print(c.val);
            if((c = c.next) == null)
                break;
            System.out.print(" -> ");
        }
    }

    static ListNode build(int... arr) {
        ListNode head = null;
        for (int i = arr.length - 1; i >= 0; i --) {
            ListNode t = new ListNode(arr[i]);
            t.next = head;
            head = t;
        }
        return head;
    }

static class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null)
            return l2;
        if(l2 == null)
            return l1;
        ListNode head = new ListNode(-1);
        ListNode c = head, next;
        while(true) {
            if(l1.val < l2.val) {
                c.next = l1;
                l1 = l1.next;
            } else {
                c.next = l2;
                l2 = l2.next;
            }
            c = c.next;
            if(l1 == null) {
                c.next = l2;
                break;
            }
            if(l2 == null) {
                c.next = l1;
                break;
            }
        }
        return head.next;
    }
}

    static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }
}